BZOJ2693 jzptab <莫比乌斯反演>

Problem

jzptab

Description

求，答案模输出。
多组询问。

Input

一个正整数表示数据组数。
接下来行，每行两个正整数表示。

Output

行，每行一个整数，表示第组数据的结果。

Sample Input

1
2

1
4 5

Sample Output

HINT

Sourse

标签：莫比乌斯反演

Solution

此题和所求相同，只是又多组询问，如果每次都像那样做为。故需要改变求和方式。这里将使用的最终推导结果来继续恒等变形。前面的推导见：BZOJ2154。

综上，的前缀和可用线性筛预处理，对于每次询问对根号分块，即可做到的复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 10000000
#define MOD 100000009
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt n, m, cnt, ans, s[MAX_N+5], pri[MAX_N+5];	bool NotPri[MAX_N+5];
void init() {
    NotPri[1] = true, s[1] = 1;
    for (lnt i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, s[i] = (i-i*i%MOD)%MOD;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) s[i*pri[j]] = s[i]*s[pri[j]]%MOD;
            else {s[i*pri[j]] = s[i]*pri[j]; break;}
        }
    }
    for (int i = 1; i <= MAX_N; i++) (s[i] += s[i-1]) %= MOD;
}
int main() {
    int T;	read(T), init();
    while (T--) {
        lnt n, m;	read(n), read(m), ans = 0;
        for (lnt l = 1, r; l <= min(n, m); l = r+1)
            r = min(n/(n/l), m/(m/l)), (ans += (n/l*(n/l+1)/2%MOD)*(m/l*(m/l+1)/2%MOD)%MOD*(s[r]-s[l-1])%MOD) %= MOD;
        printf("%lld\n", (ans+MOD)%MOD);
    }
    return 0;
}